package other;

import java.util.HashMap;


//  设计LRU缓存结构

// 当空间不足时，需要将最不常用的记录删除（插入或访问都会更新为最常用的记录），然后才能插入新记录
// key 相同时，可以直接覆盖
// 容量大小，调用构造方法设置
// 实现 get 和 set 要求时间复杂度为 O(1)

// 哈希表 + 双向链表
// 哈希表的目的是为了 访问 O(1)，哈希表中存储 key 和 结点，可以通过 key 快速访问
// 双向链表是为了插入 O(1)，同时操作的过程中，将访问到的结点移到表头，当空间不足时，删除尾部结点即可
// 将新插入的结点放到表头（头插），将访问过的结点也移到到表头

public class D230905 {
    // 设置双向链表的结点结构
    static class Node {
        int key;
        int val;
        Node pre;
        Node next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
            this.pre = null;
            this.next = null;
        }
    }

    // 哈希表
    private HashMap<Integer, Node> map = new HashMap<>();
    // 链表头节点
    private Node head = new Node(-1, -1);
    // 链表尾结点
    private Node tail = new Node(-1, -1);
    // 剩余大小
    private int size = 0;

    public D230905(int capacity) {
        this.size = capacity;
        this.head.next = this.tail;
        this.tail.pre = this.head;
    }

    // 插入函数
    public void set(int key, int val){
        if (map.containsKey(key)) {
            // 这个 key 已经存在，直接覆盖，不用判断容量了
            map.get(key).val = val;
            // 将该结点移到表头（变为最常用访问的结点）
            moveToHead(map.get(key));
        } else {
            // 新的 key，先存入 哈希表
            Node node = new Node(key, val);
            map.put(key, node);

            if (size <= 0) // 空间不足，删除最不常用的
                removeLast();
            else // 空间足够，空间 - 1
                size--;

            // 头插 进 双向链表
            insertFirst(node);
        }
    }

    // 获取数据函数
    public int get(int key){
        int res = -1;
        if (map.containsKey(key)) {
            Node node = map.get(key);
            res = node.val;
            // 将该结点移到表头
            moveToHead(node);
        }
        return res;
    }

    // 将结点移到表头
    private void moveToHead(Node node){
        if (node.pre == head) // 已经在表头了
            return;
        // 将该结点的前后结点连接
        node.pre.next = node.next;
        node.next.pre = node.pre;
        // 头插
        insertFirst(node);
    }

    // 头插
    private void insertFirst(Node node){
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
        node.pre = head;
    }

    // 删除结尾结点（删除最不常用的结点）
    private void removeLast(){
        // 删除哈希表中的数据
        map.remove(tail.pre.key);
        // 删除链表中的数据
        tail.pre = tail.pre.pre;
        tail.pre.next = tail;
    }
}
